In modern networked computing systems, user data files are often stored in networked connected data server computing devices and accessed by remote client devices through a data network such as the Internet or another suitable network. For example, numerous network-connected data storage services, sometimes referred to as “cloud” storage services, provide network-connected data storage that client computing devices use to store data files. In some instances, a client stores data on a network storage system instead of keeping a copy of the file in a local data storage device such as a hard drive or solid-state memory device.
One disadvantage of online network services is that client data may be exposed to third parties, such as network intruders, who should not be permitted access to the client information. For example, a security vulnerability in the software of a network data storage server could enable an attacker to gain access to sensitive information in files that the client has stored on the server. As is known in the art, a client computing device preserves the privacy of data files that are transmitted to the data storage server by encrypting the data files prior to storing the data files on the network storage server. The client computing device uses one or more cryptographic keys to perform the encryption, and the users of the server computing device do not have access to the cryptographic keys. When the client uses an appropriate encryption method, an attacker or other party who gains unauthorized access to the encrypted files cannot produce the original contents of the files from the encrypted files in a practical manner.
While encryption enables a client computing device to maintain the privacy of data in encrypted files that are stored on a remote server, the encryption process also presents difficulty when the client attempts to search or otherwise identify the contents of the encrypted files. As described above, in some configurations the client does not store unencrypted copies of the data files in local storage both because the local data storage device capacity may be limited in comparison to the data storage server and because the server implements redundancy and backups to preserve the encrypted files from loss. Since most security models do not place complete trust in the server, the client cannot rely on the server to decrypt and search the files without divulging the contents of the files to potential attackers.
Existing techniques including Dynamic Symmetric Searchable Encryption (DSSE) enable clients to send search queries to a server to identify encrypted files that include key words used in a search query. In a DSSE scheme, the client generates and stores one or more symmetric cryptographic keys that are not shared with the server. The client uses one key or set of keys to generate a search database of search terms corresponding to the plain text contents of the encrypted files that are stored on the server. The server stores the search database and performs searches on the encrypted files in response to requests from the client. The structure of the search database and the requests from the client do not identify the search terms that are the subject of each search request. The client uses a different key or set of keys to perform the actual encryption of the files prior to sending the encrypted files to the server. In one embodiment the search terms include commonly used words in English or words in other languages that are included in the plain text versions of the encrypted data files. In other embodiments, search terms can take the form of searchable binary data segments that may be included in multimedia files such as recorded audio, photographic, or video data files. The server stores a search database that enables the server to identify files that contain a particular search term. In existing DSSE schemes, the client generates a search query for the server that does not divulge the search term to the server and the server uses the search database to identify encrypted files that include the search term without having to decrypt the encrypted files. The client optionally retrieves one or more of the encrypted files that include the search term to decrypt the encrypted files and perform additional processing without divulging the contents of the encrypted files to the server.
A DSSE scheme is defined mathematically with the following operations: